Traditionally, software applications such as word processors, create page-based documents where each page contains graphic objects such as text, lines, fill regions and image data. When representing the document data on a display device or a printing device, such software applications typically send commands defined in terms of the graphics interface services of a native operating system within which the software application operates. The graphics interface services of the native operating system are typically known as the graphics device interface (GDI) layer. The GDI layer is generally an application programming interface (API) providing a rich set of graphics features to all applications. Typically, a graphics rendering system renders the graphics objects received from the GDI layer, generating pixels, which are then sent to the output device. Rendering is the process by which the graphics objects received from the GDI layer are converted to pixels by the graphics rendering system, which are then sent to the output device for storage, display, or printing.
Turning to FIG. 1 there is shown a traditional relationship between a prior art software application 110, a graphics device interface layer 120, a graphics rendering system 130, and an output device 140. The application 110 passes each page of a document as a series of commands defined in terms of the graphic interfaces services which describe the graphic objects of the page. The GDI layer 120 mediates between the application program 110 and the output device 140, such that the GDI layer 120 enables the graphics rendering system 130 to support a much smaller set of functionality, such as drawing rectangular blocks of image data, and filling simple regions with flat color. The GDI layer 120 also provides graphics objects to the graphics rendering system 130 in a format that the GDI layer 120 determines that the rendering system 130 would process most efficiently, and at a resolution of the output device 140. The graphics rendering system 130 then renders the graphics objects received from the GDI layer 120, generating pixels, which are then sent to the output device 140.
In some known graphic rendering systems, rendering is a two-stage process. In these rendering systems, graphics objects are first converted into an intermediate language before the rendering process begins. In one such system, the first stage of the process converts each graphic object received from the GDI layer into some intermediate edge-based object graphics format, such that all edges are sorted in ascending y, then ascending x, these corresponding respectively to the scan lines and pixel locations on such scan lines in a rasterized display. The output from this stage is typically a display list of edges and their associated fill priority (z-order), along with other information such as if this edge is a clipping edge or a filling edge. This is sometimes called a job. The job contains all the information needed by the second stage to render the page. The second stage of the process involves a rendering module parsing the job and generating the pixels for the output device for each scanline down the page.
In some GDI layers, a graphics object filled with a smooth blend of color is represented by the GDI layer as a series of adjacent single-colored parallelograms, each differing in color by some small offset from the previous, and which is clipped over the area of the graphics object. The parallelograms may proceed left to right, top to bottom or diagonally across the page.
Some applications refer to this type of fill as a gradient fill (Microsoft Word) or a fountain fill (Corel Draw). For sake of clarity, this type of fill is referred for the purposes of this description as a gradient fill. An example of a graphic object 210 filled with a diagonal gradient fill as produced by a typical prior art application is shown in FIG. 2A. The method of filling an object with a gradient fill is dependent on the application. However, in its simplest form, such a method typically consists of specifying a start color and an end color at each end of a bounding box of the graphic object being filled. FIGS. 2A, 2B, 2C illustrate how a diagonal gradient fill is typically passed by the application to the GDI layer to the graphics rendering system.
Some graphics rendering systems typically support a simple form of the gradient fill effect called a linear ramp or a linear blend. This can be represented by a starting reference point on the page, with an associated starting color, accompanied by a constant gradient change per color channel per pixel, on a line parallel to the gradient of the blend.
However, applications are generally not restricted to outputting a blend comprising a purely linear gradient fill effect. In fact, color changes in gradient fill effects produced by some applications can be parabolic or even sinusoidal. An example of an object 300 having a sinusoidal gradient fill produced by a prior art application is shown in FIG. 3.
Typically, the GDI layer reduces the gradient fill to a set of single-colored parallelograms, referred to here as fill-paths, with an accompanying clipping object. For example, FIG. 2B, shows the fill-paths and clipping object passed to the graphics rendering system by a typical prior art GDI layer, which were produced from the example gradient fill as shown in FIG. 2A. The GDI layer reduces the gradient fill to a set of single colored fill-paths 250 and a clip object 220. For sake of clarity, FIG. 2B shows only two exaggerated fill-paths 250. The entire set of the fill-paths 230 covers a rectangular area 260, with each fill-path 250 parallel to and adjoining its adjacent fill-path(s). The length of the sides of these fill-paths 250 depends on the resolution at which rendering occurs. For example, at 600 dpi, each fill-path 250 is typically no greater than 100 pixels high, but each can vary in width by several pixels. Also, each fill-path 250 has a slightly different interior color from the previous fill-path 250. This produces a smooth blend of colors associated with the gradient fill when the object is rendered. Turning now to FIG. 2C, there is shown the result of the rendering of the example shown in FIG. 2B by a typical prior art graphics rendering system. In the latter case, the rendering system has clipped the bounding box 260 comprising the fill-paths 250 with the clipping object 220 resulting in the object 210. In FIG. 2C, the result after rendering is the same as FIG. 2A.
There are a number of conventional methods for rendering such a representation of a gradient fill effect.
One conventional method is to simply render each fill-path. Many graphics rendering systems use a Painters algorithm style of rendering where each object is drawn onto a frame buffer as it arrives. A 2-stage object-graphics rendering system that firstly converts all incoming objects into some intermediate format for the page, and then renders each scanline, is at a disadvantage in rendering each fill-path. For the gradient fill shown in FIG. 2A, the GDI layer generates 128 fill-paths at 600 dpi. It can be seen that in the case of the blend proceeding top to bottom or bottom to top, then on any scanline, only one fill-path is active. But in the worst case of the blend proceeding left to right or right to left, all 128 fill-paths are active on a scanline, equating to 256 edges per scanline. Hence for an object-based rendering system, such a method of rendering is considerably inefficient. Also, each flat fill must be stored in the intermediate object-graphics format, and accessed for each fill-path for each scanline. This method consists of large amounts of memory accesses and can also consume large amounts of fill resources when the number of fill-paths is in the order of thousands. This occurs frequently when printing to pages larger than A3 at high-resolutions.
On an aesthetic level, another disadvantage of simply rendering each fill-path is that although the intended effect is clearly a smooth blend, an artifact called Mach Banding can occur. Since the eye is more sensitive to edges than it is to smooth changes in color, the eye can often see the division of rectangles when a gradient fill effect is rendered this way. The divisions become even clearer at some parts of the color gamut. Also, if the entire image is enlarged, then each fill-path is also enlarged and Mach Banding becomes highly visible.
At the application-level, another conventional method for dealing with gradient fill effects is to simply render the fill effect onto a bitmap and send this to the GDI layer. This method is effective for small fill regions, but has the disadvantage of being slower to draw and cumbersome to render since every pixel of an image has to be dealt with by the graphic rendering system. This method also does not scale well when the object is enlarged (duplication of pixels) or reduced (loss of pixels).
Another conventional method is to test each incoming fill-path for linearity and when the next fill-path is no longer linear within some error, then to create an equivalent linear blend up to this fill-path. Tracking for linearity then starts again from this next fill-path. This method can dramatically reduce the number of graphic objects needing to be rendered. In the best case scenario the entire graphic object can be described by a single linear blend. For the diagonal gradient fill as shown in FIG. 2A, this would represent a 1/128th reduction of the number of edges per scanline than if this were drawn with multiple fill-paths.
However, this method has its disadvantages. As described above, an application may provide gradient fill effects more advanced than a simple linear blend. Such effects may consist of several color changes throughout the object being filled (eg. sinusoidal as in FIG. 3), or they may follow some non-linear curve as in FIGS. 4A or 4B. Similarly, the lengths of the sides of consecutive fill-paths are not necessarily constant. In either case, the resulting set of fill-paths describing the object does not necessarily consist of a constant change in color for each fill-path even though the desired overall effect in each case is a smooth blend of color across the graphic object.
In this method an error factor is applied to determine the linearity of the next fill-path in a series of fill-paths. If the next fill-path is different to the previous fill-path by a constant difference plus or minus some error, then it is merged into the linear blend being tracked. If this error factor is too small, then it results in many linear blends, defeating the purpose of this method. If this error factor is too large, then it results in color shifting such that the output would not correctly represent the input. For example, turning to FIG. 4A there is shown a non-linear blend varying from black in the top-left corner to white in the bottom right corner, where the midpoint color between black and white is located at 25% of the distance between the top-left and bottom right corners. Also, FIG. 4B shows a similar non-linear blend, but where the midpoint color is located at 75% of the distance between the top-left and bottom right corners. If the non-linear fill-paths shown in FIGS. 4A or 4B were tracked using a large enough such error factor, then the result would be a pure linear blend from black in the top-left corner to white in the bottom-right corner as shown FIG. 4C. The result is clearly not what the user of the application intended.
Also, when the fill-paths are combined into multiple linear blends, then Mach Banding tends to become noticeable between adjacent linear blends. This banding is highly visible because the linear blends are split at their greatest error, delineating the adjacent linear blends more markedly than if individual fill-paths were rendered.